Actividad 7: Optimización heurística

Vendedor Viajero

El problema consiste en un vendedor, el cual debe hacer una recorrido por las siguientes ciudades de Colombia en su carro (no necesariamente en este orden):

Para esto vamos a utilizar dos algoritmos de optimización : Colonia de hormigas y algoritmos geneticos

Colonia de Hormigas

Los Algoritmos de Optimización por Colonias de Hormigas (ACO) son una metodología inspirada en el comportamiento colectivo de las hormigas en su búsqueda de alimentos. Veamos cómo utilizar estas características comunicativas de las colonias de hormigas para resolver un problema computacionalmente duro como es el Agente viajero

Para cada hormiga, la transición de la ciudad i a la ciudad j en una iteración del algoritmo depende de:

  1. Si la ciudad ha sido ya visitada, o no, en el ciclo que está construyendo: Cada hormiga mantiene en memoria las ciudades que ya ha visitado en el recorrido actual, y únicamente considera en cada paso las ciudades que no ha visitado todavía, que denotaremos por $J_i$. De esta forma, aseguramos que al final la hormiga ha construido un recorrido válido.

  2. La inversa de la distancia a dicha ciudad, $ν_{ij}=\frac{1}{d_{ij}}$, que es lo que se llama visibilidad: Esta medida es una información local que mide, de alguna forma, la bondad de escoger $C_j$ estando en la $C_i$, y puede ser usada por las hormigas para que la distancia entre ciudades consecutivas sea una característica que intervenga en la selección del recorrido que está construyendo. Normalmente, esta información suele ser estática, ya que las distancias de las ciudades son invariables a lo largo de la ejecución del algoritmo, pero es fácil imaginar escenarios en los que los costes de paso de un nodo a otro del grafo sean cambiantes y el algoritmo podría aplicarse para ir obteniendo buenas soluciones en este entorno dinámico.

  3. La cantidad de feromona que hay depositada en la arista que une ambos nodos, que denotaremos por $τ_{ij}(t)$: Esta cantidad se actualiza en cada paso, dependiendo de la cantidad de hormigas que han pasado por ella y de que el recorrido final de las hormigas que han usado esta conexión haya sido bueno (en relación con los demás caminos explorados). De alguna forma, mide la inteligencia colectiva del hormiguero, ya que es información que depende del conjunto de hormigas que están ejecutando el algoritmo. A diferencia de la visibilidad, esta medida proporciona una información más global, ya que la feromona que tiene una arista indica lo buena que es esa arista en conjunción con otras para dar una buena solución.

Una vez consideradas las condiciones anteriores, la probabilidad de que la hormiga k vaya de $C_i$ a $C_j$ en la construcción del recorrido actual, viene dada por una expresión del tipo siguiente:

image.png

Donde $\alpha$ y $\beta$ son dos parámetros ajustables que controlan el peso relativo de cada una de las medidas en la heurística resultante.

Implementación en python

Creamos un metodo llamado coloniaHormigas el cual tendra ciertos atributos que nos ayudaran a encontrar la solución optima

Carga de la matriz de costos

Para la construcción de esta matriz se sumo el costo de gaolina para un vehículo tipo automovil que recorre en promedio 50 km por galon, con un precio de 9000 pesos el galon, además del valor de las horas pagadas al agente por cada recorrido, acordando que el valor de la hora sería de 10000 pesos y también el valor de los peajes entre cada trayecto.

La matriz que resume estos tres criterios se presenta a continuación

Se cargan los pesos de cada trayecto y se ejecuta el metodo definido anteriormente ColoniaHormigas con los siguientes parámetros.

el costo del recorrido en cada iteraccion es:

El camino que minimiza el costo del total de recorrido iniciando en Palmira se presenta a contuniación y en el orden en que se irían visitando las ciudades :

Ilustración mejor ruta en Mapa

Ilustando el recorrido optimo del vendedor en el mapa de colombia, tenemos:

Algoritmos Geneticos

Los algoritmos genéticos funcionan iterando a lo largo de generaciones de poblaciones y evaluando qué tan bien estas poblaciones resuelven un problema. Al final de una generación, se seleccionan los mejores individuos para producir la próxima generación.

¿Cómo funciona el algoritmo?__

El concepto de individuo

Un individuo puede verse como una sola instancia del problema, en este caso es fácil ver que el individuo es la secuencia de "ciudades" y el orden en que se visitan.

Aptitud física

Los algoritmos genéticos imitan las estructuras naturales utilizando la idea de "supervivencia del más apto", por lo que es importante definir una función de aptitud común para todos los individuos. Para este caso, la aptitud de un individuo es la suma de la distancia o el valor en este caso para cada par de ciudades consecutivas, incluida la suma de la última ciudad de la secuencia y la primera.

image.png

Cargamos la información del costo que genera viajar entre cada ciudad

Implementación del algorimo

Definicimos una clase para cada una de las ciudades , la cual me permite utilizar el metodo distancia para conocer el peso o el valor que tomaría viajar entre cada ciudad

Creamos una clase que nos permite calcular la aptitud de cada indivuo, s eleccionando siempre el mejor

Funciones que nos permiten crear las rutas por las cuales se van a desplazar los individuos y calcular si distancia, además de realizar las correspondientes mutaciones

Algoritmo Genético

Con las funciones creada anteriormente iteramos el algorimo con el fin de encontrar la mejor ruta

la mejor rura es:

Ilustración mejor ruta para algoritmo genetico en Mapa de colombia